package com.moyoutian.sort;

import com.moyoutian.utils.ArrayUtils;

import java.util.Arrays;

/**
 * 快排练习3
 * 20210810
 */
public class QuickSort3 {

    public static void main(String[] args) {
        test();
    }

    /**
     * 测试程序
     */
    public static void test() {
        // 测试次数
        int testCount = 50000;
        for (int i = 0; i < testCount; i++) {
            test(ArrayUtils.getIntAr());
        }
    }

    public static void test(int[] ints) {
        int[] copy_ints_sort = Arrays.stream(ints).sorted().toArray();
        sort(ints);
        if (!Arrays.equals(copy_ints_sort, ints)) {
            System.out.println("QuickSort.test ");
        }
    }

    private static void sort(int[] ints) {
        sort(ints, 0, ints.length - 1);
    }

    private static void sort(int[] ints, int left, int right) {
        // 如果左边小于右边，证明最少两个值才进行排序
        if (left < right) {
            int temp_val = ints[right];
            int begin_right = right;
            int begin_left = left;
            while (left < right) {
                while (ints[left] < temp_val && left < right) {
                    left++;
                }
                while (ints[right] >= temp_val && left < right) {
                    right--;
                }

                ArrayUtils.swap(ints, left, right);
            }

            if (ints[right] > temp_val) {
                ArrayUtils.swap(ints, right, begin_right);
            }

            if (right + 1 < begin_right) {
                sort(ints, right + 1, begin_right);
            }
            if (begin_left < right - 1) {
                sort(ints, begin_left, right - 1);
            }
        }

    }


}
